package com.himaci.framework.adt;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;

/**
 * Kelas generic Tree
 *
 * @author XNPSDN
 * @param <T> Type kelas dalam Tree
 */
public class Tree<T> {

    public T head;
    public Tree<T> parent;
    public ArrayList<Tree<T>> leafs;
    public HashMap<T, Tree<T>> maps;

    /**
     * Konstruktor
     * @param head Elemen head
     */
    public Tree(T head) {
	this.head = head;
	parent = null;
	leafs = new ArrayList<>();
	maps = new HashMap<>();
	maps.put(head, this);
    }

    /**
     * Menambahkan daun
     * @param element Elemen yang ingin ditambahkan pada daun
     */
    public void addLeaf(T element) {
	Tree<T> leafTree = new Tree<>(element);
	leafs.add(leafTree);
	leafTree.parent = this;
	leafTree.maps = this.maps;
	maps.put(element, leafTree);
    }

    /**
     * Menambahkan daun pada elemen root tertentu
     * @param rootElement Elemen head tempat objek akan ditambahkan
     * @param element Elemen leaf yang ingin ditambahkan
     * @return True apabila berhasil (rootElement ditemukan)
     */
    public boolean addLeaf(T rootElement, T element) {
	if (maps.containsKey(rootElement)) {
	    maps.get(rootElement).addLeaf(element);
	    return true;
	}
	return false;
    }

    /**
     * Menghapus elemen pada pohon beserta seluruh sub pohonnya
     * @param element Elemen yang ingin dihapus
     * @return
     */
    public boolean remove(T element) {
	if (maps.containsKey(element) && maps.get(element).parent != null) {
	    Tree<T> elementTree = maps.get(element);
	    Tree<T> parentTree = elementTree.parent;

	    // hapus daunnya
	    parentTree.leafs.remove(elementTree);
	    removeMapping(elementTree);
	    return true;
	}
	return false;
    }

    /**
     * Menghapus mapping dari tree, sampai ke daun-daunnya
     * @param tree Tree yang seluruh elemennya ingin dihapus mappingnya
     */
    private void removeMapping(Tree<T> tree) {
	maps.remove(tree.head);
	for (Tree<T> leaf : tree.leafs) {
	    removeMapping(leaf);
	}
    }

    /**
     * Mengambil seluruh objek parent sampai root pohon
     * @param element Elemen
     * @return Koleksi elemen predecessor
     */
    public Collection<T> getPredecessor(T element) {
	Collection<T> retVal = new ArrayList<>();
	if (maps.containsKey(element)) {
	    Tree<T> temporaryTree = maps.get(element);
	    while (temporaryTree.parent != null) {
		temporaryTree = temporaryTree.parent;
		retVal.add(temporaryTree.head);
	    }
	}
	return retVal;
    }

    /**
     * Mengambil seluruh objek dalam daun pada elemen root
     * @param element Elemen
     * @return Koleksi elemen pada daun
     */
    public Collection<T> getSuccessors(T element) {
	Collection<T> retVal = new ArrayList<>();
	if (maps.containsKey(element)) {
	    Tree<T> temporaryTree = maps.get(element);
	    for (Tree<T> leaf : temporaryTree.leafs) {
		retVal.add(leaf.head);
	    }
	}
	return retVal;
    }

    /**
     * Mendapatkan kedalaman dari sebuah elemen
     * @param element Elemen yang dicari kedalamannya
     * @return -1 apabila tidak terdapat elemen yang dicari, 0 apabila berada di root
     */
    public int getDepth(T element) {
	int retVal = 0;
	if (maps.containsKey(element)) {
	    Tree<T> temporaryTree = maps.get(element);
	    while (temporaryTree.parent != null) {
		retVal++;
		temporaryTree = temporaryTree.parent;
	    }
	} else {
	    return -1;
	}
	return retVal;
    }
}
